package code;

//实际上，一个数n的最大完全平方数为sqrt(n)
public class NumSquars {
	
	//动态规划思路1：枚举最后一个可能的完全平方数
    public int numSquares1(int n) {
    	//1.状态表示：dp[i]: 平方和为n的最少数量
        //2.状态转移方程： 依次枚举可能的完全平方数，如果完全平方数<=n,则枚举
        //        则和变为dp[i-完全平方数]
        //  故此时dp[i]=min(dp[i],dp[i-完全平方数])
        if(n==1) return 1;
        //枚举[1,n]所有的完全平方和
        List<Integer> arr=new ArrayList<>();
        int tmp=1;
        //实际这里可以不写，既然后面求的是ret,那就直接在从小到大枚举即可；
        while(tmp*tmp<=n){
            arr.add(tmp*tmp);
            tmp++;
        }
        int[] dp=new int[n+1];
        Arrays.fill(dp,0x3f3f3f);
        dp[0]=0;
        dp[1]=1;
        //枚举[1,n]的每个值
        for(int i=2;i<=n;i++){
            int len=arr.size();
            //枚举完全平方和数组的下标
            for(int j=len-1;j>=0;j--){
                if(i-arr.get(j)>=0){
                    dp[i]=Math.min(dp[i],dp[i-arr.get(j)]+1);
                }        
            }
            /*   优化空间
            for(int j=1;j*j<=n;j++){
            	if(i-j*j>=0)
            	dp[i]=Math.min(dp[i],dp[i-j*j]+1);
            }
            */
        }
        return dp[n]==0x3f3f3f?n:dp[n];
    }
    
    
    //动态规划思路2： 题目等价于: 凑容量为n，每个完全平方数可以选多个 =》完全背包问题
    // 1.状态表示： 完全背包：dp[i][j]:从前i个物品中选，总体积恰好为j，所有选法的最大价值
    //            => dp[i][j]: 从前i个完全平方数中选，累加和恰好为j，所有选法中最小的完全平方数数量
    // 2.状态转移方程: 推导同完全背包模版
    //    dp[i][j]=Math.min(dp[i-1][j],dp[i][j-i*i]+1)
    // 3.初始化： 由于一定能凑成为j的体积，因此不需要-1,因为i-1可能越界，因此新增一行，多数位置填INF(因为要取min)
    // 4.返回值： dp[sqrt(n)][n]
    public int numSquares2(int n) {
    	int m=Math.sqrt(n);
    	int[][] dp=new int[m+1][n+1];
    	Arrays.fill(dp[0],0x3f3f3f);
    	dp[0][0]=0;
    	for(int i=1;i<=m;i++) {
    		for(int j=0;j<=n;j++) {
    			dp[i][j]=dp[i-1][j];
    			if(j-i*i>=0) {
    				dp[i][j]=Math.min(dp[i][j], dp[i][j-i*i]+1);
    			}
    		}
    	}
    	return dp[m][n];
    }

}
